package com.leaves.leetcode.array.t1995_CountSpecialQuadruplets;

import java.util.HashMap;
import java.util.Map;


/**
 * 核心要点：
 * 中中间分组 + **中间开始遍历** + **逆序遍历** + 哈希表
 * 1、在暴力的基础上，用Map存储nums[d]-nums[c]的组合的次数，可以减少2层O(n)的嵌套遍历
 * 2、如果像正常一样，按顺序遍历ab，那存储nums[d]-nums[c]的map在每次b改变时都要重新生成，可以考虑从b开始逆序遍历，这样每次b移动时，只需要一次循环(d)更新map中nums[d] - nums[b+1]的值即可
 * 3、左侧遍历a(O(n))，中间遍历b(O(n))，右侧dc更新(O(n))，总时间复杂度却决于左侧或右侧，但左右测时间复杂度相同，属于最佳分组
 *
 * 这里注意下，主要就是b的遍历也是遍历了c(b+1)，这时候对于cd，相当于外层先固定c，然后遍历d，在bc外层遍历下，内层遍历a和d，配合map达成O(n^2))的效果
**/
 class Solution {

    /**
     * b分组（最佳分组，左侧遍历ab 右侧dc，时间复杂度要到n^2） + 中间开始遍历 + 逆序遍历 哈希表
     * 1、在暴力的基础上，用Map存储nums[d]-nums[c]的组合的次数，可以减少2层O(n)的嵌套遍历
     * 2、如果像正常一样，按顺序遍历ab，那存储nums[d]-nums[c]的map在每次b改变时都要重新生成，可以考虑从b开始逆序遍历，这样每次b移动时，只需要一次循环(d)更新map中nums[d] - nums[b+1]的值即可
     * 3、左侧遍历a(O(n))，中间遍历b(O(n))，右侧dc更新(O(n))，总时间复杂度却决于左侧或右侧，但左右测时间复杂度相同，属于最佳分组
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(min(n, C)^2)
     * @param nums
     * @return
     */
    public int countQuadruplets(int[] nums) {
        int res = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int b = n-3; b > 0; b--) {
            for (int d = n-1; d > b+1; d--) {
                map.put(nums[d] - nums[b+1], map.getOrDefault(nums[d] - nums[b+1], 0) + 1);
            }
            for(int a = 0; a < b; a++) {
                res += map.getOrDefault(nums[a] + nums[b], 0);
            }

        }
        return res;
    }


    /**
     * c分组（不是最佳分组，左侧遍历abc 右侧d，时间复杂度要到n^3） + 中间开始遍历 + 逆序遍历 哈希表
     * 1、在暴力的基础上，用Map存储nums[d]的值出现的次数，可以减少一层O(n)的遍历
     * 2、如果像正常一样，按顺序遍历abc，那存储nums[d]的map在每次c改变时都要重新生成，可以考虑从c开始逆序遍历，这样每次c移动时，只需要更新map中nums[c+1]的值即可
     * 3、左侧遍历ab(O(n^2))，中间遍历c(O(n))，右侧d跟随c更新(O(1))，总时间复杂度却决于左侧
     * 时间复杂度：O(n^3)
     * 空间复杂度：O(min(n, C))
     * @param nums
     * @return
     */
    public int countQuadruplets_UnreasonableGrouping(int[] nums) {
        int res = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int c = n - 2; c > 1; c--) {
            map.put(nums[c+1], map.getOrDefault(nums[c+1], 0) + 1);
            for (int a = 0; a < c - 1; a++) {
                for (int b = a + 1; b < c; b++) {
                    res += map.getOrDefault(nums[a] + nums[b] + nums[c], 0);
                }
            }
        }
        return res;
    }

    /**
     * 暴力解法
     * 时间复杂度：O(n^4)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public int countQuadruplets_violence(int[] nums) {
        int res = 0;
        int n = nums.length;
        for(int a = 0; a < n-3; a++) {
            for (int b = a+1; b < n-2; b++) {
                for (int c = b+1; c < n-1; c++) {
                    for (int d = c+1; d < n; d++) {
                        if (nums[a] + nums[b] + nums[c] == nums[d]) res++;
                    }
                }
            }
        }
        return res;
    }
 }